package link;

/**
 * @Program: dataOJ->JosephurDemo
 * @Description: 约瑟夫单向环形链表
 * @Author: Tansty
 * @Date: 2022-02-07 21:25
 * @Version： 1.0
 **/

public class JosephurDemo {
    private CuteGirl first = null;

    /**
     * @param nums 生成的个数
     * @Description 生成循环链表
     * @author Tansty
     * @date 2022/2/7 21:40
     */
    public void generateList(int nums) {
        CuteGirl current = null;
        for (int i = 0; i < nums; i++) {
            CuteGirl girl = new CuteGirl(i);
            //第一个生成
            if (i == 0) {
                first = girl;
                current = first;
                continue;
            }
            //其他节点加入
            current.setNext(girl);
            current = current.getNext();
            //最后一个节点的指针要指向第一个才能形成循环链表
            current.setNext(first);
        }
    }

    public void list() {
        CuteGirl node = first;
        while (node != null) {
            System.out.println(node);
            node = node.getNext();
            //循环链表当下一个节点和第一个节点相同代表遍历到最后一个
            if (node == first) {
                break;
            }
        }
    }

    /**
     * @param startNum 开始的位置
     * @param step     每隔几个数
     * @param nums     总共的数量
     * @Description 出队
     * @author Tansty
     * @date 2022/2/7 21:39
     */
    public void outList(int startNum, int step, int nums) {
        //输入校验
        if (startNum > nums || startNum < 0 || step < 0 || first == null) {
            System.out.println("输入不合法");
            return;
        }
        //辅助指针，先指向最后一位，后面要指向要出去位置的前一位
        CuteGirl helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        while (first != helper) {
            //初始位置首先移动到位置上,辅助指针同时移动
            for (int i = 0; i < step - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.printf("%d==>", first.getNo() + 1);
            //变相删除当前该出的节点，并将first指针后移
            helper.setNext(first.getNext());
            first = first.getNext();
        }
        System.out.printf("%d", first.getNo() + 1);
    }

    public static void main(String[] args) {
        JosephurDemo demo = new JosephurDemo();
        demo.generateList(5);
        //demo.list();
        demo.outList(1, 2, 5);
    }

}

class CuteGirl {
    public CuteGirl(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "CuteGirl{" +
                "no=" + no +
                '}';
    }

    private int no;
    private CuteGirl next;

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public CuteGirl getNext() {
        return next;
    }

    public void setNext(CuteGirl next) {
        this.next = next;
    }
}
